package top100

import (
	"fmt"
	"sort"
)

func moveZeroes(nums []int) {
	var idx = 0
	for i := 0; i < len(nums); i++ {
		if nums[i] != 0 {
			nums[idx] = nums[i]
			idx++
		}
	}
	for i := idx; i < len(nums); i++ {
		nums[i] = 0
	}
}

func maxArea(height []int) int {
	var maxArea = 0
	var left = 0
	var right = len(height) - 1
	for left < right {
		var width = right - left
		var minHeight = height[left]
		if minHeight > height[right] {
			minHeight = height[right]
		}
		var curArea = width * minHeight
		if curArea > maxArea {
			maxArea = curArea
		}

		if height[left] < height[right] {
			left++
		} else {
			right--
		}
	}
	return maxArea
}

/**
 * @description: 3. 无重复字符的最长子串
 * @keyword:
 * @author: kami
 * @date 2023/12/7 9:21
 */
func lengthOfLongestSubstring(s string) int {
	var seen = make(map[uint8]int)
	var startIdx = 0
	var max = 0
	for i := 0; i < len(s); i++ {
		if idx, ok := seen[s[i]]; ok {
			if idx < startIdx {
				var diff = i - startIdx + 1
				if diff > max {
					max = diff
				}
			} else {
				startIdx = idx + 1
			}
		} else {
			var diff = i - startIdx + 1
			if diff > max {
				max = diff
			}
		}
		seen[s[i]] = i
	}
	return max
}
func findAnagrams(s, p string) (ans []int) {
	sLen, pLen := len(s), len(p)
	if sLen < pLen {
		return
	}

	var sCount, pCount [26]int
	for i, ch := range p {
		sCount[s[i]-'a']++
		pCount[ch-'a']++
	}
	if sCount == pCount {
		ans = append(ans, 0)
	}

	for i, ch := range s[:sLen-pLen] {
		sCount[ch-'a']--
		sCount[s[i+pLen]-'a']++
		if sCount == pCount {
			ans = append(ans, i+1)
		}
	}
	return
}

func setZeroes(matrix [][]int) {
	var zeroI = make(map[int]struct{})
	var zeroJ = make(map[int]struct{})

	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[i]); j++ {
			if matrix[i][j] == 0 {
				zeroI[i] = struct{}{}
				zeroJ[j] = struct{}{}
			}
		}
	}

	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[i]); j++ {
			if _, ok := zeroI[i]; ok {
				matrix[i][j] = 0
			} else if _, ok1 := zeroJ[j]; ok1 {
				matrix[i][j] = 0
			}
		}
	}
}

/**
 * @description: 54. 螺旋矩阵
 * @keyword:
 * @author: kami
 * @date 2023/12/9 16:57
 */
func spiralOrder(matrix [][]int) []int {
	var rowMin = 0
	var rowMax = len(matrix) - 1
	var colMin = 0
	var colMax = len(matrix[0]) - 1
	var res []int
	for {
		// 右
		for i := colMin; i <= colMax; i++ {
			res = append(res, matrix[rowMin][i])
		}
		rowMin++
		if rowMin > rowMax {
			break
		}

		// 下
		for i := rowMin; i <= rowMax; i++ {
			res = append(res, matrix[i][colMax])
		}
		colMax--
		if colMax < colMin {
			break
		}
		// 左
		for i := colMax; i >= colMin; i-- {
			res = append(res, matrix[rowMax][i])
		}
		rowMax--
		if rowMax < rowMin {
			break
		}

		// 上
		for i := rowMax; i >= rowMin; i-- {
			res = append(res, matrix[i][colMin])
		}
		colMin++
		if colMin > colMax {
			break
		}
	}
	return res
}

/**
 * @description: 41. 缺失的第一个正数
 * @keyword:
 * @author: kami
 * @date 2023/12/9 21:24
 */
func firstMissingPositive(nums []int) int {
	n := len(nums)
	for i := 0; i < n; i++ {
		if nums[i] <= 0 {
			nums[i] = n + 1
		}
	}
	for i := 0; i < n; i++ {
		num := abs(nums[i])
		if num <= n {
			fmt.Println(num - 1)
			nums[num-1] = -abs(nums[num-1])
		}
	}
	for i := 0; i < n; i++ {
		if nums[i] > 0 {
			return i + 1
		}
	}
	return n + 1
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func merge(intervals [][]int) [][]int {
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})

	var res [][]int
	res = append(res, intervals[0])
	for i := 1; i < len(intervals); i++ {
		pre := res[len(res)-1]
		if intervals[i][0] > pre[1] {
			res = append(res, intervals[i])
		} else {
			if intervals[i][1] > pre[1] {
				pre[1] = intervals[i][1]
			}
		}
	}

	return res
}

type ListNode struct {
	Val  int
	Next *ListNode
}

func detectCycle(head *ListNode) *ListNode {
	if head == nil || head.Next == nil || head.Next.Next == nil {
		return nil
	}

	var slow = head
	var fast = head
	for slow != fast {
		if fast.Next == nil || fast.Next.Next == nil {
			return nil
		}
		fast = fast.Next.Next
		slow = slow.Next
	}
	var start = head
	for start != slow {
		start = start.Next
		slow = slow.Next
	}
	return start
}

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	var virtualHead = new(ListNode)
	var preNode = virtualHead
	var cur1 = list1
	var cur2 = list2
	for cur1 != nil && cur2 != nil {
		if cur1.Val < cur2.Val {
			preNode.Next = cur1
			cur1 = cur1.Next
		} else {
			preNode.Next = cur2
			cur2 = cur2.Next
		}
		preNode = preNode.Next
	}

	if cur1 != nil {
		preNode.Next = cur1
	}
	if cur2 != nil {
		preNode.Next = cur2
	}
	return virtualHead.Next
}

func letterCombinations(digits string) []string {
	var res []string
	var dfs func(nums string, index int, curRes []byte)

	dfs = func(nums string, index int, curRes []byte) {
		if len(curRes) == len(nums) {
			var temp = make([]byte, len(curRes))
			copy(temp, curRes)
			res = append(res, string(temp))
			return
		}
		for i := index; i < len(nums); i++ {
			var letters = getLetterByDigit(nums[i])
			for j := 0; j < len(letters); j++ {
				curRes = append(curRes, letters[j])
				dfs(nums, i+1, curRes)
				curRes = curRes[0 : len(curRes)-1]
			}
		}
	}

	dfs(digits, 0, []byte{})
	return res
}

func getLetterByDigit(digit byte) string {
	switch digit {
	case '2':
		return "abc"
	case '3':
		return "def"
	case '4':
		return "ghi"
	case '5':
		return "jkl"
	case '6':
		return "mno"
	case '7':
		return "pqrs"
	case '8':
		return "tuv"
	default:
		return "wxyz"
	}
}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func maxPathSum(root *TreeNode) int {
	if root == nil {
		return 0
	}
	var max = root.Val
	var dfs func(node *TreeNode) int
	dfs = func(node *TreeNode) int {
		if node == nil {
			return 0
		}
		var left = dfs(node.Left)
		if left < 0 {
			left = 0
		}
		var right = dfs(node.Right)
		if right < 0 {
			right = 0
		}
		var curSum = node.Val + left + right
		if curSum > max {
			max = curSum
		}
		if left > right {
			return node.Val + left
		}
		return node.Val + right
	}
	dfs(root)
	return max
}
